package com.topcoder.srm520;

public class SRMSystemTestPhase {
	public int countWays(String[] description) {
		int MOD = 1000000007;
		int N = description.length;
		int[][][] dp = new int[N+1][4][4];
		
		for (int maxP = 3; maxP >= 0; maxP--) {
			for (int minC = 0; minC < 4; minC++) {
				dp[N][maxP][minC] = 1;
			}
		}
		
		for (int row = N-1; row >= 0; row--) {
			boolean p0 = description[row].charAt(0)=='Y';
			boolean p1 = description[row].charAt(1)=='Y';
			boolean p2 = description[row].charAt(2)=='Y';
			int outcome0 = p0? 3:1;
			int outcome1 = p1? 3:1;
			int outcome2 = p2? 3:1;
			
			for (int i = 0; i < outcome0; i++) {
				for (int j = 0; j < outcome1; j++) {
					for (int k = 0; k < outcome2; k++) {
						int pass = 0, challenge = 0;
						if (p0 && i == 0)
							pass++;
						if (p0 && i == 2)
							challenge++;
						if (p1 && j == 0)
							pass++;
						if (p1 && j == 2)
							challenge++;
						if (p2 && k == 0)
							pass++;
						if (p2 && k == 2)
							challenge++;

						for (int maxP = pass; maxP < 4; maxP++) {
							for (int minC = 0; minC < 4; minC++) {
								if (maxP > pass || challenge >= minC) {
									dp[row][maxP][minC] = (dp[row][maxP][minC] + dp[row + 1][pass][challenge]) % MOD;
								}
							}
						}
					}
				}
			}
			
		}
		
		return dp[0][3][0];
	}
	
	
	// ------------------------------------------------------------------------
	// topcoder solution
	// ------------------------------------------------------------------------
	static int M = 1000000007;
	static String[] rows;

	public int countWays2(String[] s) {
		rows = s;
		for (int i = 0; i < 51; i++)
			for (int j = 0; j < 4; j++)
				for (int k = 0; k < 4; k++)
					dp[i][j][k] = -1;
		return dp(0, 3, 0);
	}

	int[][][] dp = new int[51][4][4];

	public int dp(int r, int max_passed, int min_challenged) {
		if (r == rows.length)
			return 1;
		if (dp[r][max_passed][min_challenged] >= 0)
			return dp[r][max_passed][min_challenged];
		int ans = 0;
		int lim_i = rows[r].charAt(0) == 'Y' ? 3 : 1;
		int lim_j = rows[r].charAt(1) == 'Y' ? 3 : 1;
		int lim_k = rows[r].charAt(2) == 'Y' ? 3 : 1;
		for (int i = 0; i < lim_i; i++)
			for (int j = 0; j < lim_j; j++)
				for (int k = 0; k < lim_k; k++) {
					int passed = 0;
					int challenged = 0;
					if (rows[r].charAt(0) == 'Y' && i == 0)
						passed++;
					if (rows[r].charAt(0) == 'Y' && i == 1)
						challenged++;
					if (rows[r].charAt(1) == 'Y' && j == 0)
						passed++;
					if (rows[r].charAt(1) == 'Y' && j == 1)
						challenged++;
					if (rows[r].charAt(2) == 'Y' && k == 0)
						passed++;
					if (rows[r].charAt(2) == 'Y' && k == 1)
						challenged++;
					if (passed > max_passed || passed == max_passed
							&& challenged < min_challenged)
						continue;
					ans = (ans + dp(r + 1, passed, challenged)) % M;
				}
		return dp[r][max_passed][min_challenged] = ans;
	}
}
